
//合并两个有序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* dfs(ListNode* l1,ListNode* l2)
    {
        if(l1 == nullptr) return l2;
        else if(l2 == nullptr) return l1;
        if(l1->val > l2->val)
        {
            l2->next = dfs(l1,l2->next);
            return l2;
        }
        else 
        {
            l1->next = dfs(l1->next,l2);
            return l1;
        }

    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
            return dfs(list1,list2);
    }
};

//反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void dfs(ListNode* head,ListNode*& tail)
    {
        if(head->next == nullptr)
        {
            tail = head;
            return;
        }
        dfs(head->next,tail);
        head->next->next = head;
        head->next = nullptr;

    }
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* ret;
        dfs(head,ret);
        return ret;
    }
};

//两两交换链表中的节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
         if(head == nullptr || head->next == nullptr) return head;
         ListNode* temp = head->next->next;
         head->next->next = head;
         ListNode* next = head->next; head->next = swapPairs(temp);
         return next;
         
    }
};

//Pow(x,n)
class Solution {
public:
    double Pow(double x , long long n)
    {
        if(n == 0) return 1;
        
        if(n % 2 == 0 )
        {
            double tmp = Pow(x,n/2);
            return tmp * tmp;
        }
        else 
        {
            double tmp = Pow(x,n/2);
            return tmp * tmp * x;
        }
    }
    double myPow(double x, int n) {
        if(n > 0)
        {
            return Pow(x,n);
        }
        else 
        {
            return 1 / Pow(x,static_cast<long long>(n)*(-1));
        }
    }
};



